#include <bits/stdc++.h>

using namespace std;
#define MAX_SRC_P 80
#define ROOT_ID 0

int main(int argc, char **argv) {
    FILE *p1, *p2;
    int vertex_num, edge_num;
    int *edge_offset_mem_array, *edge_mem_array, *vertex_p;
    int updated;
    char message [100];

    if (argc != 3) {
        cout << "Usage: Parameter (offset_file, info_file)." << endl;
        exit (-1);
    }

	if ((p1 = fopen(argv[1], "r")) == NULL) {
        cout << "[ERROR] Failed to open file " << argv[1] << endl;
        exit(-1);
    }
    cout << "[INFO] Open file " << argv[1] << endl;

	if ((p2 = fopen(argv[2], "r")) == NULL) {
        cout << "[ERROR] Failed to open file " << argv[2] << endl;
        exit(-1);
    }
    cout << "[INFO] Open file " << argv[2] << endl;

	fscanf(p1, "%d", &vertex_num);
    fscanf(p2, "%d", &edge_num);
    cout << "[INFO] Vertex_num = " << vertex_num << ", Edge_num = " << edge_num << endl;

    edge_offset_mem_array = (int *) calloc (vertex_num + 1, sizeof(int));
    edge_mem_array = (int *) calloc (edge_num, sizeof(int));
    vertex_p = (int *) calloc (vertex_num, sizeof(int));

	for (int i = 0; i < (vertex_num + 1); ++ i) {
	    fscanf(p1, "%d", &edge_offset_mem_array[i]);
	    if (i && (edge_offset_mem_array[i] == edge_offset_mem_array[i - 1])) {
            cout << "[ERROR] Offset Init: Vertex " << i << ", Off_l = " << edge_offset_mem_array[i - 1] << ", Off_r = " << edge_offset_mem_array[i] << endl;
            exit (-1);
        }
	}

	for (int i = 0; i < edge_num; ++ i) fscanf(p2, "%d", &edge_mem_array[i]);

	fclose(p1);
	fclose(p2);

    for (int i = 0; i < vertex_num; ++ i) vertex_p[i] = MAX_SRC_P;
    vertex_p[ROOT_ID] = 0;

    double st = 0;

    double t1 = 0;
    double t2 = 0;
	for (int iter = 0; iter < 20; ++ iter) {
        updated = 0;

        t1 = clock();
        int count = 0;
        for (int i = 1; i < vertex_num; ++ i) {
            int left = edge_offset_mem_array[i];
            int right = edge_offset_mem_array[i + 1];
            int tmp = MAX_SRC_P;

            for (int j = left; j < right; ++ j) {
                if (edge_mem_array[j] >= vertex_num) {
                    tmp = min (tmp, MAX_SRC_P);
                } else {
                    tmp = min (tmp, vertex_p[edge_mem_array[j]] + 1);
                }
            }

            if (tmp < vertex_p[i]) {
                updated = 1;
                count ++;
            }
            vertex_p[i] = min(vertex_p[i], tmp);
        }
        cout << "Updata Count = " << count << endl;

        if (!updated) {
            cout << "[INFO] Max iterator number = " << iter << endl;
            break;
        }
        t2 = clock();
        cout << (t2 - t1) * 1.0 / CLOCKS_PER_SEC * 1000 << endl;
        st += (t2 - t1) * 1.0 / CLOCKS_PER_SEC * 1000;
	}
    cout << "sum = " << st << endl;
}
